ABC032 D - ナップサック問題

提出

code: python

n, w = map(int, input().split())

for i in range(n):

for j in range(w + 1):

# 入らないのでそのまま

else:

# i番目の品物を入れなかった場合を比較

解答

code: python

from bisect import *

from collections import defaultdict

n, w = map(int, input().split())

vl, wl = [], []

for vi, wi in vw:

vl.append(vi)

wl.append(wi)

# print(vl, wl)

# 半分全列挙

def solve1():

d1 = defaultdict(int)

for bit in range(2 ** len(vl1)):

tmpv = 0

tmpw = 0

for i in range(len(vl1)):

if (bit >> i) & 1:

# print(d1)

# defaultdict(<class 'int'>, {0: 0, 9: 15})

d2 = defaultdict(int)

for bit in range(2 ** len(vl2)):

tmpv = 0

tmpw = 0

for i in range(len(vl2)):

if (bit >> i) & 1:

# print(d2)

# defaultdict(<class 'int'>, {0: 0, 6: 10, 4: 6, 10: 16})

# d2 において、各重量で達成できる最大の価値が連続して増加するように

d2w = sorted(d2.keys())

for i in range(len(d2w) - 1):

# print(d2)

# defaultdict(<class 'int'>, {0: 0, 6: 10, 4: 6, 10: 16})

res = 0

for w1 in d1:

if w1 > w:

continue

# d2 の keys のうち、残りの重量制限を超えない最大のキーの位置

j = bisect_right(d2w, w - w1)

return res

# wを横軸にしたDP

def solve2():

for i in range(n):

for j in range(w, wi - 1, -1):

# vを横軸にしたDP

def solve3():

maxv = n * 1000

for i in range(n):

for j in range(maxv, vi-1, -1):

res = 0

for i in range(maxv + 1):

res = i

return res

if n <= 30:

print(solve1())

elif max(wl) <= 1000:

print(solve2())

else:

print(solve3())

テーマ

メモ

提出

code: python

n, w = map(int, input().split())

# print(vw)

# 全探索: O(pow(2, n))

for i in range(1, n+1):

for j in range(w+1):